/*
 * @lc app=leetcode.cn id=542 lang=typescript
 *
 * [542] 01 矩阵
 */

// @lc code=start
class Data {
  i: number;
  j: number;
  l: number;
  constructor(i: number = 0, j: number = 0, l: number = 0) {
    this.i = i;
    this.j = j;
    this.l = l;
  }
}

function updateMatrix(mat: number[][]): number[][] {
  const dir = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1],
  ];
  const n = mat.length;
  const m = mat[0].length;
  const visited: number[][] = new Array(n).fill(0).map(() => new Array(m).fill(-1));
  const queue: Data[] = [];
  // 将元素值为0的坐标加入队列
  const initQueue = (queue: Data[], mat: number[][], visited: number[][]) => {
    for (let i = 0; i < mat.length; i++) {
      for (let j = 0; j < mat[i].length; j++) {
        if (mat[i][j] !== 0) continue;
        visited[i][j] = 0;
        queue.push(new Data(i, j, 0));
      }
    }
  };

  initQueue(queue, mat, visited);

  while (queue.length) {
    const data = queue.shift();
    for (let k = 0; k < dir.length; k++) {
      const x = data.i + dir[k][0];
      const y = data.j + dir[k][1];
      if (x < 0 || x >= n) continue;
      if (y < 0 || y >= m) continue;
      if (visited[x][y] !== -1) continue;
      visited[x][y] = data.l + 1;
      queue.push(new Data(x, y, data.l + 1));
    }
  }

  return visited;
}
// @lc code=end
